// 题目描述
// 1081. 不同字符的最小子序列
// 提示
// 中等
// 199
// 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
//   示例 1：
// 输入：s = "bcabc"
// 输出："abc"
// 示例 2：
// 输入：s = "cbacdcbc"
// 输出："acdb"
//   提示：
// 1 <= s.length <= 1000
// s 由小写英文字母组成
//   注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同
// 通过次数
// 27.7K
// 提交次数
// 47.3K
// 通过率
// 58.5%
// https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters

/**
 * @param {string} s
 * @return {string}
 */
var smallestSubsequence = function (s) {
  const sLen = s.length

  const lastIndex = {}
  for (let i = 0; i < sLen; i++) {
    lastIndex[s[i]] = i
  }

  const sk = [], peek = () => sk[sk.length - 1]
  const visited = {}
  for (let i = 0; i < sLen; i++) {
    const ch = s[i]

    if (visited[ch]) {
      continue
    }

    while (sk.length && peek() > ch && lastIndex[peek()] > i) {
      visited[sk.pop()] = false
    }

    sk.push(ch)
    visited[ch] = true
  }

  return sk.join('')
}

console.log(
  smallestSubsequence(
    'cbacdcbc'
  )
)

